#include <ctype.h>
#include <limits.h>
#include <stddef.h>
#include <stdarg.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <float.h>
#include <signal.h>
#include <setjmp.h>
#include <errno.h>
#include <assert.h>
#include <math.h>

#include <stdexcept>
#include <typeinfo>
#include <algorithm>

#include <list>
#include <map>
#include <vector>
#include <string>
using std::string;
using std::wstring;

#include <unistd.h>
#include <net/if.h>
#include <sys/types.h>
#include <sys/param.h>
#include <sys/time.h>
#include <sys/stat.h>
#include <sys/prctl.h>
#include <sys/socket.h>
#include <sys/epoll.h>
#include <sys/ioctl.h>
#include <netinet/in.h>
#include <netinet/tcp.h>
#include <arpa/inet.h>
#include <netdb.h>
#include <fcntl.h>

#include <pthread.h>

class List
{
public:

    class Node
    {
    public:
        Node *prev;
        Node *next;
    };

    List()
    {
        root = new Node();
        root->prev = root;
        root->next = root;
    }

    ~List()
    {
        delete root;
    }

    inline void insert(Node *prev, Node *next, Node *node)
    {
        next->prev = node;
        node->next = next;
        node->prev = prev;
        prev->next = node;
    }

    inline Node *erase(Node *node)
    {
        node->next->prev = node->prev;
        node->prev->next = node->next;
		return node;
    }

    inline bool empty() const
    {
        return root->next == root;
    }

    inline void push_front(Node *node)
    {
        insert(root, root->next, node);
    }

    inline void push_back(Node *node)
    {
        insert(root->prev, root, node);
    }

    inline Node *pop_front()
    {
        if (empty())
            return NULL;

        return erase(root->next);
    }

    inline Node *pop_back()
    {
        if (empty())
            return NULL;

        return erase(root->prev);
    }

private:
    Node *root;
};

